package work;
//Description:时间复杂度和空间复杂度
/**
 * 1.用常数1取代运行时间中的所有加法常数
 * 2.在修改后的一些次数函数中，只保留最高阶项
 * 3.如果最高阶项存在且不是1 则除去这个项目相乘的常数
 * 得到的结果就是大o阶 使用大o的渐进表示法以后，则时间复杂度是这个
 *
 *
 * 最坏情况 任意输入规模的最大运行次数（平时讨论都是最坏的）
 * 平均情况 任意输入规模的期望运行次数（根据代码的情况给出平均时间复杂度）
 * 最好情况 任意规模的最小运行次数
 */

public class Main {
    void fun(int N,int M){
        int a = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                a++;
            }//时间复杂度为N^2 看循环

            /**
             * 二分查找最坏是log以二为底n的对数（n/（2^x）=1 求x）
             * 递归的时间复杂度=递归的次数*每次递归执行的次数
             * 菲波那切数列 每两项相加等于前一项第一次为f（n）第二次为f（n-1）和f（n-2）
             * 第三次为f（n-1-1）和f（n-1-2）。。。。。直到f（n-(n-1)）。。最坏情况是全部都填满
             * 则 时间复杂度应为（2^0 + 2^1 +...2^n-1）=1*(1-2^n)/-1=2^n+1则时间复杂度为2^n
             */

            /**
             * 空间复杂度
             * 冒泡排序法空间复杂度为o（1）没有随着问题的规模而变量增加
             */
        }
    }
    long[] fibonacci(int n){
        long[] a = new long[n + 1];
        a[0] = 0;
        a[1] = 1;
        for (int i = 2; i < n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a;
    }
     //空间复杂度为o（n） 需要存储每一项
     long factorial(int n){//阶乘递归
        return n < 2?n:factorial(n-1)*n;
     }
     //空间复杂度为o(n)为每一项都开辟了空间


    public static void main(String[] args) {

        //System.out.println(System.currentTimeMillis());
    }
}
